#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE  10
typedef int Elemtype;
typedef struct BiTNode{
    Elemtype data;
    struct BiTNode *lchild;
    struct BiTNode * rchild;
}BiTNode,*BiTree;

typedef struct SqStack
{
	BiTree data[MAXSIZE];
	int top;
}SqStack,*Stack;
//创建栈
Stack InitStack()
{
	Stack S;
	S = (Stack)malloc(sizeof(SqStack));
	S->top = -1;
	return S;
}
//栈空
int isEmpty(Stack S)
{
	if (S->top == -1)return 1;
	else return 0;
}
//入栈
void Push (Stack S,BiTree p)
{
	S->top++;
	S->data[S->top] = p;
}
//出栈
void Pop(Stack S, BiTree* p)
{
	*p = S->data[S->top];
	S->top--;
}

void visit(Elemtype data){
    printf(" %d ",data);
}

void preOrder(BiTree T){
    BiTNode *pNode = T;
    Stack stack =  InitStack();
    while (pNode!=NULL || !isEmpty(stack))
    {
        if(pNode){
            Push(stack,pNode);
            visit(pNode->data);
            pNode = pNode->lchild;
            
        }else{
            Pop(stack,&pNode);
            pNode = pNode->rchild;
        }
    }
}


void inOrder(BiTree T){
    BiTNode *pNode = T;
    Stack stack =  InitStack();
    while (pNode!=NULL || !isEmpty(stack))
    {
        if(pNode){
            Push(stack,pNode);
            pNode = pNode->lchild;
            
        }else{
            Pop(stack,&pNode);
            visit(pNode->data);
            pNode = pNode->rchild;
        }
    }
}

void postOrder(BiTree T){
    BiTNode * pNode = T ,*r= NULL;
    Stack stack = InitStack();
    while (pNode!=NULL || !isEmpty(stack))
    {
       if(pNode){
            Push(stack,pNode);
            pNode = pNode->lchild;
       }else{
            Pop(stack,&pNode);
            Push(stack,pNode);
            if(pNode->rchild && pNode->rchild!= r){
                pNode = pNode->rchild;
                Push(stack,pNode);
                pNode = pNode->lchild;
            }else{
                Pop(stack,&pNode);
                visit(pNode->data);
                r = pNode;
                pNode = NULL;    
            }
       }
    }
    
}

BiTNode * createBiTree(Elemtype preOrderarr[],int preFirst,int preLast,Elemtype inOrder[],
int inFirst,int inLast){
    if(preFirst > preLast){
        return NULL;
    }

    BiTNode * root = (BiTNode*)malloc(sizeof(BiTNode));
    root->data = preOrderarr[preFirst];
    int rootIndex;
    for ( rootIndex = inFirst; rootIndex <= inLast; rootIndex++)
    {
       if(inOrder[rootIndex] == root->data){
        break;
       }
    }
    BiTNode *lchild = createBiTree(preOrderarr,preFirst+1,preFirst+rootIndex-inFirst,inOrder,inFirst,rootIndex-1);
    BiTNode *rchild = createBiTree(preOrderarr,preFirst+rootIndex-inFirst+1,preLast,inOrder,rootIndex+1,inLast);
    root->lchild = lchild;
    root->rchild = rchild;
    return root;
}

typedef struct node
{
    BiTNode* data;
    struct node *next;
}node;

typedef struct Queue{
    node *front;
    node *rear;
}Queue;

node* initNode(){
    node *n = (node*)malloc(sizeof(node));
    return n; 
}

Queue* initQueue(){
    Queue *q = (Queue*)malloc(sizeof(Queue));
    q->front = NULL;
    q->rear = NULL;
    return q;
}

int isQEmpty(Queue *q){
    if(q->front ==NULL){
        return 1;
    }
    return 0;
}
//入队
void EnQueue(Queue*q,BiTNode*data){
    node *n = initNode();
    n->data = data;n->next = NULL;
    if(isQEmpty(q)){
        q->front = n;
        q->rear = n;
    }else{
        q->rear->next = n;
        q->rear = n;
    }

}
//出队
BiTNode * DeQueue(Queue *q){
    node *n = q->front;
    if(isQEmpty(q)){
        return NULL;
    }
    BiTNode* res = n->data;
    if(q->front == q->rear){
        q->front = NULL;
        q->rear = NULL;
    }else{
        q->front = q->front->next;
    }
    free(n);
    return res;

}

void levelTraverse(BiTree T){
        Queue *Q = initQueue();
        if(T!=NULL){
            EnQueue(Q,T);
        }
        while (!isQEmpty(Q))
        {
           BiTNode*e = DeQueue(Q);
           visit(e->data);
           if(e->lchild!=NULL){
            EnQueue(Q,e->lchild);
           }
           if(e->rchild!=NULL){
            EnQueue(Q,e->rchild);
           }
        }
}

int main(){
    int preArr[MAXSIZE] = {1,2,4,5,7,3,6};
    int inArr[MAXSIZE] = {4,2,7,5,1,3,6}; 
    BiTree T =  createBiTree(preArr,0,6,inArr,0,6);
  postOrder(T);
  //levelTraverse(T);
}